我們已經介紹完了 Queue 和 Stack，今天大部分是程式碼，要來看看 Stack 要怎麼製作 Queue，以及如何用 Queue 實作 Stack。

利用 Stack 製作 Queue

我們會用 2 個 Stack 來製作，分別是 s1 以及 s2。
enqueue: 如果 s1 滿了，那麼代表 Queue 已滿。否則，直接 push 到 s1 堆疊中。
dequeue: 重點實作項目。如果 s2 是空的話，就將 s1 的元素依序 pop 及 push 進 s2，這是由於堆疊具有**反序 reverse **的特性。原本元素在 s1 的底端，透過這樣的動作，將會變成在 s2 的頂端，符合 Queue 的 FIFO 特性。那如果 s2 不為空的話，代表上次 reverse 的元素還沒輸出完。直接 pop s2 頂端元素即可。

程式碼：這次直接使用 C++ 的 stack library

#include <iostream>
#include <stack>
#include <limits.h>

using namespace std;

class Queue{
    private:
        stack<int> s1;
        stack<int> s2;
    public:
        void enqueue(int item);
        int dequeue();
};

void Queue::enqueue(int item){
    s1.push(item);
}

int Queue::dequeue(){
    if(s2.empty()){
        if(s1.empty()){
            cout << "dequeue fail." << endl;
            return INT_MIN;
        }else{
            while(!s1.empty()){
                int temp = s1.top();
                s1.pop();
                s2.push(temp);
            }
            int ans = s2.top();
            s2.pop();
            return ans;
        }
    }else{
        int temp = s2.top();
        s2.pop();
        return temp;
    }
}

這樣的時間複雜度，大多是 O(1)，只有在少數時間（s2 空又要 dequeue 時）才會到 O(n) 時間。

利用 Queue 製作 Stack

只需要一個 Queue 即可製作。

push: 若 Queue 沒滿，直接 enqueue 進 queue 中。
pop: 重點實作。假設目前 queue 中有 n 個元素，當 pop 時，將前面 n - 1 個元素依序 dequeue 再 enqueue 至 Queue 尾端，這樣最後加入的元素就會在 queue 的前端。

程式碼：直接使用 C++ 的 queue library

#include <iostream>
#include <queue>
#include <limits.h>

using namespace std;

class Stack{
    private:
        queue<int> q;
    public:
        void push(int item);
        int pop();
};

void Stack::push(int item){
    q.push(item);
}

int Stack::pop(){
    if(q.empty()){
        cout << "pop fail." << endl;
        return INT_MIN;
    }
    for(int i = 0; i < q.size() - 1; i++){
        int temp = q.front();
        q.pop();
        q.push(temp);
    }
    int k = q.front();
    q.pop();
    return k;
}

到今天為止已經介紹完 Queue 和 Stack 了。明天開始進入 Tree ！